package one.stack;

import java.util.Stack;

/**
 * 最小栈
 */
public class MinStack {
    //思路：使用两个栈。一个存数据，一个存最小值。
    //时间复杂度：O(1)
    private Stack stack;
    private Stack minStack;
    /** initialize your data structure here. */
    public MinStack() {
        this.stack = new Stack();
        this.minStack = new Stack();
    }

    public void push(int val) {
        stack.push(val);
//        System.out.println(stack.peek() + " val:" + val);

        int min = Math.min((minStack.empty() ? val : (int)minStack.peek()), val);
        minStack.push(min);
//        System.out.println(Math.min((int)stack.peek(), val));
    }

    public void pop() {
        stack.pop();
        minStack.pop();
    }

    public int top() {
        return (int)stack.peek();
    }

    public int getMin() {
        return (int)minStack.peek();
    }

    public static void main(String[] args) {
        MinStack test = new MinStack();
        test.push(1);
        test.push(2);
        test.push(3);
        System.out.println(test.top() + "   " + test.getMin());
    }
}
